#include <string>
#include <stack>

using namespace std;
// 思路： 使用栈来匹配括号
//     遍历字符串，遇到左括号就入栈，遇到右括号就判断栈顶元素是否匹配，匹配则出栈，否则返回false
class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto &c : s)
        {
            if (c == '(' || c == '{' || c == '[') // 左括号入栈
            {
                st.push(c);
            }
            else if (!st.empty() && isMatch(st.top(), c)) // 右括号匹配栈顶元素
            {
                st.pop();
            }
            else // 不匹配
            {
                return false;
            }
        }
        if (st.empty()) // 栈为空则匹配成功
        {
            return true;
        }
        return false;
    }
    bool isMatch(char &left, char &right)
    {
        if (left == '(' && right == ')')
        {
            return true;
        }
        else if (left == '[' && right == ']')
        {
            return true;
        }
        else if (left == '{' && right == '}')
        {
            return true;
        }
        return false;
    }
};